package HashTable;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class _438_FindAllAnagramsinaString {
    //reference web:https://www.cnblogs.com/grandyang/p/6014408.html
    int patternLength = 0;
    String pattern = "";
    boolean[] check = {};
    Set<String> patternSet = new HashSet<String>();
    //solution 1:use set to get every possible pattern,
    //time limit exceeded
    public List<Integer> findAnagrams_0(String s, String p) {
        List<Integer> results = new ArrayList<>();
        if (p.length() > s.length()) {
            return results;
        }
        this.pattern = p;
        this.patternLength = pattern.length();
        this.check = new boolean[patternLength];
        getPattern("",check);
        for (int i = 0; i <= s.length()-patternLength; i++) {
            String temp = s.substring(i, i + patternLength);
            if (patternSet.contains(temp)) {
                results.add(i);
            }
        }
        return results;
    }

    public void getPattern(String temp,boolean[] check) {
        if (temp.length() == patternLength) {
            patternSet.add(temp);
        } else {
            for (int i = 0; i < patternLength; i++) {
                if (!check[i]) {
                    check[i] = true;
                    String newTemp = temp + pattern.charAt(i);
                    getPattern(newTemp,check);
                    check[i] = false;
                }
            }
        }
        return;
    }

    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> results = new ArrayList<>();
        int lens = s.length(), lenp = p.length();
        int count = lenp;
        if (lenp > lens) {
            return results;
        }
        int[] list = new int[26];
        for (char c:p.toCharArray()) {
            list[c - 'a']++;
        }
        for (int i = 0; i < lenp; i++) {
            list[s.charAt(i) - 'a']--;
            if (list[s.charAt(i) - 'a'] >= 0) {
                count--;
            }
        }
        if (count == 0) {
            results.add(0);
        }
        int bg = 0;
        for (int i = lenp; i <lens ; i++) {
            list[s.charAt(i)-'a']--;
            if (list[s.charAt(i) - 'a'] >= 0) {
                count--;
            }
            list[s.charAt(bg) - 'a']++;
            if (list[s.charAt(bg++) - 'a'] > 0) {
                count++;
            }
            if (count == 0) {
                results.add(bg);
            }
        }
        return results;
    }


}
